/*
 * @lc app=leetcode.cn id=391 lang=cpp
 *
 * [391] 完美矩形
 */
#include "include.h"
// @lc code=start

// 扫描线

// 将每个矩形rectangles[i]看做两条竖直方向的边，使用(x, y1, y2)的形式进行存储（其中 y1 代表该竖边的下端点，y2 代表竖边的上端点），
// 同时为了区分是矩形的左边还是右边，再引入一个标识位，即以四元组 (x,y1,y2,flag) 的形式进行存储。

// 一个完美矩形的充要条件为：对于完美矩形的每一条非边缘的竖边，都「成对」出现
// （存在两条完全相同的左边和右边重叠在一起）；对于完美矩形的两条边缘竖边，均独立为一条连续的（不重叠）的竖边。

class Solution {
public:
    bool isRectangleCover(vector<vector<int>>& rectangles) {
        int min_x = 1e5+1;
        int max_x = -1e5-1;
        int min_y = 1e5+1;
        int max_y = -1e5-1;

        // <x, map_column>
        //     <<y1, y2>, flagCounter>
        //                flagCounter : left +1, right -1, => left + right = 0
        // std::map<int, std::map<std::pair<int, int>, int>> scanLine;

        // <x, map_column>
        //     <y, delta> 
        //                left +1 ___|---\___
        //               right -1 ---\___|---
        std::map<int, std::map<int, int>> scanLine;

        for (int i=0;i<rectangles.size();++i){
            int left = rectangles[i][0];
            int bottom = rectangles[i][1];
            int right = rectangles[i][2];
            int top = rectangles[i][3];

            min_x = std::min(min_x, left);
            max_x = std::max(max_x, right);
            min_y = std::min(min_y, bottom);
            max_y = std::max(max_y, top);

            scanLine[left][bottom] += 1;
            scanLine[left][top] -= 1;
            scanLine[right][bottom] -= 1;
            scanLine[right][top] += 1;
        }

// for (auto& vertical : scanLine) {
//     printf("x %d ", vertical.first);
//     for (auto& lineDelta : vertical.second) {
//         printf("(%d : %d) ", lineDelta.first, lineDelta.second);
//     }
//     printf("\n");
// }

        for (auto& vertical : scanLine) {
            auto& deltaArray = vertical.second;

            if (vertical.first == min_x or vertical.first == max_x) {
                // check edge continue / no overlap

                // check lost range
                if (deltaArray.find(min_y) == deltaArray.end() or
                    deltaArray.find(max_y) == deltaArray.end()) {return false;}
                
                // left : min_y : +1 and max_y : -1
                if (vertical.first == min_x and
                    (deltaArray[min_y] != 1 or
                    deltaArray[max_y] != -1)) {return false;}
                // right : min_y : -1 and max_y : +1
                if (vertical.first == max_x and
                    (deltaArray[min_y] != -1 or
                    deltaArray[max_y] != 1)) {return false;}
                
                // else all = 0
                for (auto& lineDelta : deltaArray) {
                    if (lineDelta.first == min_y or lineDelta.first == max_y) {continue;}
                    if (lineDelta.second != 0) {return false;}
                }
            } else {
                // not edge , all = 0
                for (auto& lineDelta : deltaArray) {                
                    if (lineDelta.second != 0) {return false;}
                }
            }
        }

        return true;
    }
};

// @lc code=end

struct LeafNode;
// segtree node is just a range [start, end)
struct SegTreeNode
{
    // [start, end)
    int start, end;

    SegTreeNode *left, *right;
    LeafNode* leafPtr = nullptr;
    SegTreeNode() : start(0), end(0), left(nullptr), right(nullptr){}
    SegTreeNode(int from, int to) : start(from), end(to), left(nullptr), right(nullptr){}
    SegTreeNode(int from, int to, int tracked) : start(from), end(to), left(nullptr), right(nullptr){}
};
// put data into leaf
struct LeafNode
{
    SegTreeNode* segTreePtr;
    // LeafNode* prev;
    LeafNode* next;
    
    // <y, delta>
    std::map<int, int> columnInfo;
    LeafNode() : segTreePtr(nullptr), next(nullptr) {}
    LeafNode(SegTreeNode* infoPtr) : segTreePtr(infoPtr), next(nullptr) {}
};

class axisManager {
public:
    SegTreeNode* root_;
    LeafNode* leafHead_;
public:
    axisManager() {
        root_ = new SegTreeNode(-1e5-1, 1e5+1);
        leafHead_ = new LeafNode(root_);
        root_->leafPtr = leafHead_;
    }
    ~axisManager() {
        clearTree(root_);
        clearList(leafHead_);
    }
public:
    // return : seg => x ~ [start, end)
    SegTreeNode* split(int x) {
        SegTreeNode* root = findBelongingLeft(x, root_);
        if (x == root->start) {return root;}
        // if (x == root->end) {return root->leafPtr->next->segTreePtr;}

        root->left = new SegTreeNode(root->start, x);
        root->right = new SegTreeNode(x, root->end);

        // use origin as left
        LeafNode* origin = root->leafPtr;
        // use new one as right
        LeafNode* temp = new LeafNode(root->right);
        // share same column info
        temp->columnInfo = origin->columnInfo;

        temp->next = origin->next;
        origin->next = temp;
        origin->segTreePtr = root->left;
        // temp->segTreePtr = root->right;

        root->leafPtr = nullptr;
        root->left->leafPtr = origin;
        root->right->leafPtr = temp;

        return root->left;
    }
    // return : start <= x < end, default from root
    SegTreeNode* findBelongingLeft(int x) {
        return findBelongingLeft(x, root_);
    }
    // return : start < x <= end, default from root
    SegTreeNode* findBelongingRight(int x) {
        return findBelongingRight(x, root_);
    }
private:
    // return : start <= x < end
    SegTreeNode* findBelongingLeft(int x, SegTreeNode* root){
        if (root->left and root->right){
            if (x < root->right->start){return findBelongingLeft(x, root->left);}
            else {return findBelongingLeft(x, root->right);}
        }else{
            return root;
        }
    }
    // return : start < x <= end
    SegTreeNode* findBelongingRight(int x, SegTreeNode* root){
        if (root->left and root->right){
            if (x <= root->right->start){return findBelongingRight(x, root->left);}
            else {return findBelongingRight(x, root->right);}
        }else{
            return root;
        }
    }
private:
    void clearTree(SegTreeNode* root){
        // post order traverse
        if (root->left){clearTree(root->left);}
        if (root->right){clearTree(root->right);}
        // do
        delete root;
    }
    void clearList(LeafNode* leaf){
        if (!leaf) {return;}
        clearList(leaf->next);
        delete leaf;
    }
};

class SolutionFool {
public:
        // 直接统计vertex出现次数，密铺情况下除了大包络角点，其他的只可能出现2或4次
        // 然后查面积相等
    bool isRectangleCover(vector<vector<int>>& rectangles) {
        int min_x = 1e5+1;
        int max_x = -1e5-1;
        int min_y = 1e5+1;
        int max_y = -1e5-1;

        axisManager x_axis;

        for (int i=0;i<rectangles.size();++i){
            int left = rectangles[i][0];
            int bottom = rectangles[i][1];
            int right = rectangles[i][2];
            int top = rectangles[i][3];

            min_x = std::min(min_x, left);
            max_x = std::max(max_x, right);
            min_y = std::min(min_y, bottom);
            max_y = std::max(max_y, top);

            // todo : need optimize here
            x_axis.split(left);
            x_axis.split(right);

            auto rightBelonging = x_axis.findBelongingRight(right)->leafPtr;
            auto leftBelonging = x_axis.findBelongingLeft(left)->leafPtr;

            for (auto leafPtr=leftBelonging;leafPtr!=rightBelonging->next;leafPtr=leafPtr->next) {
                leafPtr->columnInfo[bottom] += 1;
                leafPtr->columnInfo[top] -= 1;
            }
        }

        // check holo / overlap
        auto leafPtr = x_axis.leafHead_;

        while (leafPtr) {
            auto& columnDelata = leafPtr->columnInfo;

            if (leafPtr->segTreePtr->start >= min_x and
                leafPtr->segTreePtr->end <= max_x and
                columnDelata.empty()) {
                // printf("x holo %d ~ %d\n", leafPtr->segTreePtr->start, leafPtr->segTreePtr->end);
                return false;}
            
            int z_height = 0;
            int y_start = 0;
            int y_end = 0;

            // check column from min_y to max_y , height == 1
            for (auto& delta : columnDelata) {
                int y = delta.first;

                int z_before = z_height;
                z_height += delta.second;
                int z_after = z_height;

                if (z_height > 1) {
                    // printf("y %d height %d deltaHeight %d\n", y, z_before, delta.second);
                    return false;}
                if (z_before == 0 and z_after > 0) {
                    y_start = y;
                    if (y_start != min_y) {
                        // printf("y_start %d y_min %d\n", y_start, min_y);
                        return false;}
                }
                if (z_before > 0 and z_after == 0) {
                    y_end = y;
                    if (y_end != max_y) {
                        // printf("y_end %d y_max %d\n", y_end, max_y);
                        return false;}
                }
            }
            
            leafPtr = leafPtr->next;
        }

        return true;
    }
};
